package tree;


import commons.TreeNode;

/**
 * leet-code(236) 二叉树的最近公共祖先
 *
 * @author Ringo
 * @date 2021/8/14 14:39
 */
public class LowestCommonAncestor {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return dfs(root, p, q);
    }

    public TreeNode dfs(TreeNode x, TreeNode p, TreeNode q) {
        if (x == null || x == p || x == q)
            return x;
        TreeNode left = dfs(x.left, p, q);
        TreeNode right = dfs(x.right, p, q);
        if (left == null) return right;
        if (right == null) return left;
        return x;
    }
}
